const tree = {
  val: "a",
  children: [
    {
      val: "b",
      children: [
        {
          val: "d",
          children: [],
        },
        {
          val: "e",
          children: [],
        },
      ],
    },
    {
      val: "c",
      children: [
        {
          val: "f",
          children: [],
        },
        {
          val: "g",
          children: [],
        },
      ],
    },
  ],
};

// 深度优先遍历
// 访问根节点
// 对根节点的 children 挨个进行深度优先遍历
const dfs = (root) => {
  console.log(root.val);
  root.children.forEach(dfs);
};

// a b d e c f g
dfs(tree);

// 广度优先遍历
const bfs = (root) => {
  // 1. 新建一个队列，把根节点入队
  const q = [root];

  // 4. 重复2、3，直到队列为空
  while (q.length > 0) {
    // 2. 把队头出队并访问
    const n = q.shift();
    console.log(n.val);
    // 3. 把队头的 children 挨个入队
    n.children.forEach((child) => {
      q.push(child);
    });
  }
};

// a b c d e f g
bfs(tree);
